<TITLE>prob011: ACC basketball schedule</TITLE>
<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>prob011: ACC basketball schedule</H1>

<TABLE>
<TR> <TD> proposed by
     <TD ALIGN=LEFT> <A HREF="http://www.cs.york.ac.uk/~tw">
          <B>Toby Walsh</B></A> 
          <ADDRESS><a href="mailto:tw@cs.york.ac.uk">
          tw@cs.york.ac.uk</a></ADDRESS>
</TABLE>
</CENTER>
<HR><!------------------------------------------------------------------------>
<H3> Specification </H3>

<TT>
The problem is finding a timetable for the
1997/98 Atlantic Coast Conference (ACC) in basketball.
It was first tackled by Nemhauser and Trick.

<P>
The 9 basketball teams in the tournament 
are Clemson (Clem), Duke (Duke), Florida State (FSU)
, Georgia Tech (TT), Maryland (UMD), North Carolina (UNC), North Carolina State 
(NCSt), Virginia (UVA), and Wake Forest (Wake).
The problem is to determine a double round robin 
schedule for these 9 teams subject to some additional
constraints. In a double round robin, each team places
each other, once at home, once away. The schedule
is to be played over 18 dates.
The first and all subsequent odd dates are weekday 
fixtures. The second and all subsequent even dates
are weekend fixtures. There are nine other sets
of constraints.

<P>
<B>1. Mirroring</B>. 
The dates are grouped into pairs (r1, r2), such that each team will
get to play against the same team in dates r1 and r2. Such a grouping is called
a mirroring scheme. Nemhauser and Trick use the mirroring scheme
{(1, 8), (2, 9), (3, 12), (4, 13), (5, 14), (6, 15), (7, 16), (10, 17), (11, 18)}

<P>
<B>2. No Two Final Aways</B>. 
No team can play away on both last dates.

<P>
<B>3. Home/Away/Bye Pattern Constraints</B>. 
No team may have more than two 
away matches in a row. No team may have more than two home matches in a row. 
No team may have more than three away matches or byes in a row. 
No team may have more than four home matches or byes in a row.

<P>
<B>4. Weekend Pattern</B>. 
Of the weekends, each team plays four at home, four away,
and one bye.

<P>
<B>5. First Weekends</B>. 
Each team must have home matches or byes at least on two
of the first five weekends.

<P>
<B>6. Rival Matches</B>. 
Every team except FSU has a traditional rival. The rival pairs
are Duke-UNC, Clem-GT, NCSt-Wake, and UMD-UVA. In the last date, every team 
except FSU plays against its rival, unless it plays against FSU or has a bye.

<P>
<B>7. Constrained Matches</B>. 
The following pairings must occur at least
once in dates 11 to 18: Wake-UNC, Wake-Duke, GT-UNC, and GT-Duke.

<P>
<B>8. Opponent Sequence Constraints</B>. 
No team plays in two consecutive dates
away against UNC and Duke. 
No team plays in three consecutive dates against UNC,
Duke and Wake (independent of home/away).

<P>
<B>9. Other Constraints</B>. 
UNC plays its rival Duke in the last date and in
date 11. UNC plays Clem in the second date. Duke has a bye in date 16. Wake does
not play home in date 17. Wake has a bye in the first date. Clem, Duke, UMD and
Wake do not play away in the last date. Clem, FSU, GT and Wake do not play away 
in the first date. Neither FSU nor NCSt have a bye in last date. UNC does not have a bye in the first date.

</TT>


<HR><!------------------------------------------------------------------------>

<UL>

 <A HREF="../../index.html"> Back</A> to CSPLib home page.


